//1.按输入顺序进行排列，而不是全排列，注意顺序！！！！！
class Solution {
public:
    vector<string> ans;
    string temp;
    // 索引与数字直接对应，mapping[2] == "abc"
    vector<string> mapping = {
        "", "", "abc", "def", "ghi",
        "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    // 递归函数，i 表示当前处理到 digits 中的位置
    void dfs(const string &digits, int i) {
        if (i == digits.size()) {
            ans.push_back(temp);
            return;
        }
        int num = digits[i] - '0';
        const string &letters = mapping[num];
        for (char c : letters) {
            temp.push_back(c);
            dfs(digits, i + 1);
            temp.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.empty())
            return {};
        dfs(digits, 0);
        return ans;
    }
};
